#include "List.h"

// 双向链表创建新节点

LTNode* LTBuyNode (LTDataType x)
{

    LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)) ;

    if (newnode == NULL)
    {

        perror ("malloc fail!") ;

        exit (1) ;

    }

    newnode -> data = x ;

    newnode -> prev = newnode -> next = newnode ; // 这里双向链表和单链表的创建差别体现在了指针指向的是空还是自己

    return newnode ;

}

// 双向链表的初始化

// void LTInit (LTNode** pphead)
// {

//     assert (pphead && *pphead) ;

//     *pphead = LTBuyNode (-1) ;

// }

LTNode* LTInit ()
{

    LTNode* phead = LTBuyNode (-1) ;

    return phead ;

}

// 双向链表的销毁

// void LTDestory (LTNode** pphead)
// {

//     LTNode* pcur = (*pphead) -> next ; // 这里的链表由于是双向链表,所以尾节点可以找到头节点,我们可以只创建一个指针,让指针一个个销毁直到最后在头结点销毁

//     while (pcur != *pphead)
//     {
        
//         LTNode* next = pcur -> next ; // 创建坐标

//         free (pcur) ;

//         pcur = next ;

//     }

//     free (*phead) ;

//     *pphead = NULL ;

// }

void LTDestory (LTNode* phead)
{

    LTNode* pcur = phead -> next ;

    while (pcur != phead)
    {

        LTNode* next = pcur -> next ;

        free (pcur) ;

        pcur = next ;

    }

    free (phead) ;

    phead = NULL ;
        
}

// 双向链表的尾插(适用只有一个节点的情况)

void LTPushBack (LTNode* phead , LTDataType x)
{

    assert (phead) ;

    LTNode* newnode = LTBuyNode (x) ;

    // 双向链表 phead可以找到phead -> prev (尾节点),再连newnode

    newnode -> prev = phead -> prev ;

    newnode -> next = phead ;

    phead -> prev -> next = newnode ;

    phead -> prev = newnode ;

}

// 双向链表的尾删

void LTPopBack (LTNode* phead)
{

    assert (!LTEmpty (phead)) ; // 这里防止链表为空链表,不然删不了

    LTNode* del = phead -> prev ;

    // phead del -> prev del 将del独立出来再释放

    del -> prev  -> next = phead ;

    phead -> prev = del -> prev ;

    free (del) ;

    del = NULL ;
    
}

// 双向链表的头插

void LTPushFront (LTNode* phead , LTDataType x)
{

    assert (phead) ;

    LTNode* newnode = LTBuyNode (x) ;

    // phead newnode  phead -> next,相当于头结点的尾插

    newnode -> next = phead -> next ;

    newnode -> prev = phead ;

    phead -> next -> prev = newnode ;

    phead -> next = newnode ;

}

// 双向链表的头删

void LTPopFront (LTNode* phead)
{

    assert (!LTEmpty (phead)) ;

    LTNode* del = phead -> next ;

    // phead del del -> next ;

    del -> next -> prev = phead ;

    phead -> next = del -> next ;

    free (del) ;

    del = NULL ;

}

// 双向链表pos位置之后插入数据

void LTInsert (LTNode* pos , LTDataType x)
{

    assert (pos) ;

    LTNode* newnode = LTBuyNode (x) ;

    // pos newnode pos -> next 

    newnode -> next = pos -> next ;

    newnode -> prev = pos ;

    pos -> next -> prev = newnode ;

    pos -> next = newnode ;

}

// 双向链表指定位置之前插入数据

void LTInsertFront (LTNode* pos , LTDataType x)
{

    assert (!LTEmpty (pos)) ; // 这里情况和尾插不一样,如果是空节点就不能头插?

    LTNode* newnode = LTBuyNode (x) ;

    // pos -> prev newnode pos

    newnode -> prev = pos -> prev ;

    newnode -> next = pos ;

    pos -> prev -> next = newnode ;

    pos -> prev = newnode ;

}

// 双向链表删除pos位置的节点

void LTErase (LTNode* pos)
{

    assert (pos) ;

    // pos -> prev pos pos -> next

    pos -> next -> prev = pos -> prev ;

    pos -> prev -> next = pos -> next ;

    free (pos) ;

    pos = NULL ;

}

// 查找双向链表的节点
// 找到就返回该节点,找不到就返回NULL

LTNode* LTFint (LTNode* phead , LTDataType x)
{

    LTNode* pcur = phead -> next ;

    while (pcur != phead)
    {

        if (pcur -> data == x)
        {

            return pcur ;

        }

        pcur = pcur -> next ;

    }

    return NULL ;
    
}

// 判断双向链表是否为空
// 只有一个头结点的情况下,双向链表为空

bool LTEmpty (LTNode* phead)
{

    assert (phead) ;

    return phead -> next == phead ; // 这里如果链表为空,头结点的下一个节点就是自己 所以我们这里设立判断语句并返回结果,如果是空则true否则false

}

// 双向链表的打印(需要注意双向链表不同于单链表,有头结点的概念)

void LTPrint (LTNode* phead)
{

    LTNode* pcur = phead -> next ;

    while (pcur != phead) // 这里要注意,双向链表有头结点(哨兵位) 其结点没有数据,所以要略过 而且可以作为循环结束的条件(双向链表是环状)
    {

        printf ("%d -> " , pcur -> data) ;

        pcur = pcur -> next ;

    }

    printf ("NULL\n") ;    

}
